package com.hdu.other.dp.treeDP;


import java.util.ArrayList;
import java.util.List;

public class lc2246 {
    class Solution {
        public int longestPath(int[] parent, String s) {
            int len = parent.length;
            List<List<Integer>> g = new ArrayList<>();
            for (int i = 0; i < len; i++) {
                g.add(new ArrayList<>());
            }
            for (int i = 1; i < len; i++) {
                g.get(parent[i]).add(i);
            }
            return f(s.toCharArray(), g, 0).maxHeight;
        }

        Info f(char[] s, List<List<Integer>> tree, int x) {
            if (tree.get(x).isEmpty()) {
                return new Info(1, 1);
            }
            int max1 = 0;
            int max2 = 0;
            int maxHeight = 1;

            for (int i = 0; i < tree.get(x).size(); i++) {
                Info info = f(s, tree, tree.get(x).get(i));
                maxHeight = Math.max(maxHeight, info.maxHeight);
                if (s[x] != s[tree.get(x).get(i)]) {
                    if (info.maxHeightFromHead > max1) {
                        max2 = max1;
                        max1 = info.maxHeightFromHead;
                    }
                    else if (info.maxHeightFromHead > max2) {
                        max2 = info.maxHeightFromHead;
                    }
                }
            }

            maxHeight = Math.max(maxHeight, max1 + max2 + 1);
            return new Info(
                    max1 + 1,
                    maxHeight
            );
        }

        class Info {
            int maxHeightFromHead;
            int maxHeight;

            public Info(int maxHeightFromHead, int maxHeight) {
                this.maxHeightFromHead = maxHeightFromHead;
                this.maxHeight = maxHeight;
            }
        }
    }
}
